package 简单.分类讨论;

import util.TreeNode;

/**
 * 你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
 * <p>
 * 空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/construct-string-from-binary-tree
 */
public class 根据二叉树创建字符串_606 {

    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);

        root.left = node2;
        root.right = node3;
        node2.left = node4;
        System.out.println(tree2str(root));

    }

    /**
     * 递归+分类讨论
     * 如果当前节点有左右子节点，(a)(b)
     * 如果当前节点只有左子节点，那么右子节点可以省略，(a)
     * 如果当前节点只有右子节点，那么左子节点不能省略，()(b)
     * 对于[root,left,right]来说
     * --> root(left)(right)
     *
     * @param root
     * @return
     */
    public static String tree2str(TreeNode root) {
        if (root == null) {  //确定停止条件
            return "";
        }
        if (root.left == null && root.right == null) {  //对于最后一层无需添加括号
            return String.valueOf(root.val);
        }
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(root.val);  //前序遍历先遍历主节点，对于主节点来说，无需被括号包裹
        if (root.left != null && root.right != null) {
            return stringBuilder.append("(").append(tree2str(root.left)).append(")")
                    .append("(").append(tree2str(root.right)).append(")").toString();
        }
        if (root.left != null) {
            return stringBuilder.append("(").append(tree2str(root.left)).append(")").toString();
        }
        return stringBuilder.append("()").append("(").append(tree2str(root.right)).append(")").toString();
    }


}
